package com.hy.treeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class TreeNodeLevelOrderByAvg {


    /**
     * 637.二叉树的层平均值
     * 力扣题目链接
     *
     * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
     *
     * 思路:
     *
     * 本题就是层序遍历的时候把一层求个总和在取一个均值。
     *
     */

    public List<Double> levelOrderByAvg(TreeNode root){
        List<Double> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null){
            return res;
        }
        deque.addLast(root);

        while (!deque.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            int len = deque.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = deque.pollFirst();
                temp.add(node.val);

                if (node.left != null){
                    deque.addLast(node.left);
                }
                if (node.right != null){
                    deque.addLast(node.right);
                }
            }
            res.add(temp.stream().mapToDouble(x->x.intValue()).sum()/len);
        }
        return res;
    }



    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        TreeNodeLevelOrderByAvg treeNodeLevelOrder = new TreeNodeLevelOrderByAvg();
        System.out.println("层序遍历->二叉树的层平均值 : "+treeNodeLevelOrder.levelOrderByAvg(root));
    }
}
